package A06_递归;

/**
 * 走迷宫：从最左上角，走到最右下角
 * 移动策略：下 ->右 -> 上 -> 左
 * @Author: KingWang
 * @Date: 2021/6/7
 * @Desc:
 **/
public class MigongDemo {

    private static int step = 0;
    public static void main(String[] args) {

        //定义二维数组，制作围墙,并在围墙中增加障碍物
        int rows=8, cols=12;
        int[][] map = new int[rows][cols];

        //制定围墙
        for (int i = 0; i < cols; i++) {
            map[0][i] = 1;
            map[rows-1][i] = 1;
        }
        for (int i = 0; i < rows; i++) {
            map[i][0] = 1;
            map[i][cols-1] = 1;
        }

        //设置挡板
        map[2][1]=1;
        map[2][2]=1;

        //增加障碍物
        for (int i = 2; i < 7 ; i++) {
            map[4][i] = 1;
        }

        System.out.println("==============开始迷宫=================");
        showMap(map);
        move(map,1,1);
        System.out.println("============== 迷宫走完,共移动了步数："+step+" ================");
        showMap(map);

    }

    //展示地图
    public static void showMap(int[][] map){
        for(int[] arr:map){
            for(int i:arr){
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }


    //约定：使用1表示围墙，使用0表示未走过，使用2表示已经走过的，使用3表示走过但是走不通的
    //循环迭代二维数组：行走策略：下右上左
    //移动 策略：下右上左
    public static boolean move(int[][] map,int i,int j){

        //如果已经走通
        if(map[6][10] == 2){
            return true;
        }

        //如果这个位置没走过
        if(map[i][j] == 0){
            //按策略下右上左
            map[i][j] = 2;  //假定能走通
            if(move(map,i+1,j)){ //下
                step++;
                return true;
            }else if(move(map,i,j+1)){  //右
                step++;
                return true;
            }else if(move(map,i-1,j)){  //上
                step++;
                return true;
            }else if(move(map,i,j-1)){  //左
                step++;
                return true;
            }else{
                //说明走不通
                map[i][j] = 3;
                return false;
            }

        }
        return false;
    }


}
